Farey Algorithm for Approximating Transcendentals

The Farey is conceptually very simple. Consider a transcendental (or irrational) number's fractional part. This number lies somewhere between 0/1 and 1/1. Add these numbers in a unique way (0+1)/(1+1) and the resulting fraction is guaranteed to lie between the original fractions. Using this unique addition always produces a number that lies between the two starting fractions. It is called the mediant.

Farey's algorithm uses this property to find rational approximations of transcendental numbers. For instance, if one is approximating π, then take the fractional part, 0.1415..., and start with the same two fractions as above. You now have three fractions, 0/1, 1/2, and 1/1. The desired fraction lies between 0/1 and 1/2. Drop the 1/1 and repeat the unique addition with 0/1 and 1/2 to get 1/3. Our number lies between 0/1 and 1/3, so repeat with these fractions to get 1/4. About 10,000 repetitions later you should have a very accurate rational approximation of π once you correctly add the three back to the fraction.

The calculator returns the best rational approximation to the selected transcendental based on the limit provided by the user.

I am not sure if there is a reasonable limit. The algorithm is very fast. Errors go to zero before 100 iterations except for π. It is above 0 at 500 iterations.




Select a transcendental and enter a limit: